package ygw.study.advanced.sort;

import org.junit.Test;
import ygw.study.advanced.sort.common.SortUtils;

/**
 * <p>
 * 希尔排序
 * </p>
 * <p>
 * Copyright:2021.All rights reserved.
 * </p>
 * <p>
 * Company:Zsoft
 * </p>
 * <p>
 * CreateDate:2021-05-25 12:51
 * </p>
 *
 * @author YuGongWen
 * @history Mender:YuGongWen；Date:2021-05-25 12:51；
 */
public class ShellSort {
    //核心代码---开始
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }

    @Test
    public void test() {
//        Integer[] arr = SortUtils.gennerateArray(10000,90000000);
        Integer[] arr = SortUtils.gennerateArray(10, 100);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            System.out.print(' ');
        }
        ShellSort.sort(arr);
        System.out.println("\n排序后");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}